📋 Problem Statement
You are building the backend of a financial platform that records users' daily transactions over N days. Each transaction can be positive (deposit) or negative (withdrawal). Support:
- Efficient querying of total transaction amount between two days
- Updating transaction amount on a specific day
📥 Input Format
- First line: N (days) and Q (operations)
- Second line: N space-separated integers (transaction amounts)
- Next Q lines: Operations
- S L R - Query sum from index L to R
- U i val - Update index i with value val
🎯 Sample Test Case 1
Input:6 5 10 -5 20 15 -10 5 S 0 2 U 1 7 S 0 2 S 3 5 S 0 5Output:
25 37 10 47Explanation:
- S 0 2: Sum of [10, -5, 20] = 25
- U 1 7: Update index 1 from -5 to 7
- S 0 2: Sum of [10, 7, 20] = 37
- S 3 5: Sum of [15, -10, 5] = 10
- S 0 5: Sum of all = 47
🧠 Segment Tree Algorithm
📊 Key Operations
- Build: Construct segment tree in O(n) time
- Query: Get range sum in O(log n) time
- Update: Modify value in O(log n) time
💻 C++ Implementation
class SegmentTree {
vector<int> tree;
int n;
void build(vector<int>& arr, int node, int start, int end) {
if (start == end) {
tree[node] = arr[start];
} else {
int mid = (start + end) / 2;
build(arr, 2*node+1, start, mid);
build(arr, 2*node+2, mid+1, end);
tree[node] = tree[2*node+1] + tree[2*node+2];
}
}
int query(int l, int r, int node, int start, int end) {
if (r < start || end < l) return 0;
if (l <= start && end <= r) return tree[node];
int mid = (start + end) / 2;
return query(l, r, 2*node+1, start, mid) +
query(l, r, 2*node+2, mid+1, end);
}
};
⚡ Complexity Analysis
- Build: O(n) - construct tree once
- Query: O(log n) - binary tree traversal
- Update: O(log n) - path from leaf to root
- Space: O(n) - 4n tree nodes maximum
📊 Current Array State
🌳 Segment Tree Structure
⚙️ Current Operation
Status
Ready to build tree...
Operation log will appear here...
📤 Query Results
-